#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
 // 1 2 3 4
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
示例 2：

输入：n = 1, k = 1
输出：[[1]]
 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combinations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * */


vector<vector<int>> ret;

vector<int> path;//存储的路径 1 2  //  1 3
void backer(int n, int k, int index) {
    //寻找出口
    if (path.size() == k) {
        ret.push_back(path);
        return;
    }

    //一个for + 递归把整棵树全都遍历了 不用外部循环了
    for (int i = index; i <= n - (k - path.size()) + 1; ++i) {
        path.push_back(i);//把当前的加入
        backer(n, k, i + 1);//继续寻找下一个 路径（寻找下一个拼凑数字）
        //这边也是关键点 相当于是找到了12 然后找完之后把 2弹出 继续循环找
        path.pop_back(); //如果此时为 1 4  都找完了 这时候到14 此时成 数组path成一个1 （此时index是4）这边循环也结束了

    }


}


vector<vector<int>> combine(int n, int k) {
    backer(n, k, 1);
    return ret;

}


//第二道题
static vector<vector<int>> result; // 存放结果集
static vector<int> path; // 符合条件的结果
// targetSum：目标和，也就是题目中的n。
// k：题目中要求k个数的集合。
// sum：已经收集的元素的总和，也就是path里元素的总和。
// startIndex：下一层for循环搜索的起始位置。
void backtracking(int targetSum, int k, int sum, int startIndex) {
    if (path.size() == k) {
        if (sum == targetSum) result.push_back(path);
        return; // 如果path.size() == k 但sum != targetSum 直接返回
    }
    for (int i = startIndex; i <= 9; i++) {
        sum += i; // 处理
        path.push_back(i); // 处理
        backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
        sum -= i; // 回溯
        path.pop_back(); // 回溯
    }
}

vector<vector<int>> combinationSum3(int k, int n) {
    result.clear(); // 可以不加
    path.clear();   // 可以不加
    backtracking(n, k, 0, 1);
    return result;
}